package com.datastructures2.graph.有向图;

import com.datastructures2.graph.最短路径.DirectedEdge;
import com.datastructures2.graph.最短路径.EdgeWeightedDigraph;
import edu.princeton.cs.algs4.AcyclicSP;

/**
 * 拓扑排序
 * @author MaoLin Wang
 * @date 2020/2/2215:04
 */
public class TopologicalSort {
    //顶点的拓扑排序
    private Iterable<Integer>order;

    public TopologicalSort(Digraph digraph) {
        DirectedCycle directedCycle=new DirectedCycle(digraph);
        if (!directedCycle.hasCycle()){
            //返回拓扑排序
            DepthFirstOrder dfs=new DepthFirstOrder(digraph);
            order=dfs.reversePost();
        }

    }
    public TopologicalSort(EdgeWeightedDigraph digraph){
        EdgeWeightedDirectedCycle directedCycle=new EdgeWeightedDirectedCycle(digraph);
        if (!directedCycle.hasCycle()){
            DepthFirstOrder dfs=new DepthFirstOrder(digraph);
            order=dfs.reversePost();
        }
    }

    public Iterable<Integer>order(){
        return order;
    }
    public boolean hasOrder(){
        return order!=null;
    }
}
